package chapter02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsWithDup90 {
    /**
     * 回溯法
     * 去重问题都要先排序
     * 回溯想象成一棵树 分为树层去重 和 树枝去重
     * 本题元素在同一个组合内是可以重复的 怎么重复都没事 但两个组合不能相同
     * 所以我们要去重的是同一树层上的“使用过” 同一树枝上的都是一个组合里的元素 不用去重。
     * 为了区分某一元素是否使用过 增加一个boolean数组
     * process(nums,pos,path) 当前来到nums下标pos位置
     * 在某一层上
     *  i->[pos,nums.length-1]
     *  如果[pos]和[pos-1]值相同并且[pos-1]没有使用过 说明同一层上已回溯过[pos] 跳过当前下标pos
     *  否则path添加[i] [i]标记已使用 继续回溯下一个i+1位置 i+1回溯结束尝试同一层其他元素时 将[i]从path取出 [i]标记未使用
     * 递归出口
     *  求子集结果集中没有固定数值 进入递归时就可以将当前path直接加入res中 再进行下一个回溯
     *  如果 pos>=nums.length 本次分支回溯就可以结束 return
     */
    List<List<Integer>> res;
    boolean[] isUsed;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if(nums==null||nums.length==0){
            return res;
        }
        res=new ArrayList<>();
        isUsed=new boolean[nums.length];
        Arrays.sort(nums);
        process(nums,0,new ArrayList<>());
        return res;
    }

    public void process(int[] nums,int pos,List<Integer> path){
        res.add(new ArrayList<>(path));
        if(pos>=nums.length){
            return;
        }
        for(int i=pos;i<nums.length;i++){
            if(i>pos&&nums[i]==nums[i-1]&&!isUsed[i-1]){
                continue;
            }
            isUsed[i]=true;
            path.add(nums[i]);
            process(nums,i+1,path);
            isUsed[i]=false;
            path.remove(path.size()-1);
        }
    }
}
